#include <vector>
#include <unordered_map>
using namespace std;
// 思路：前缀和 + 哈希表
// https://leetcode.cn/problems/subarray-sum-equals-k/?envType=study-plan-v2&envId=top-100-liked
// 1. 使用一个哈希表来存储前缀和及其出现的次数，初始时将前缀和0的出现次数设为1。
// 2. 遍历数组，计算当前的前缀和prefix_sum。
// 3. 对于每个前缀和prefix_sum，计算目标前缀和target = prefix_sum - k。
// 4. 检查哈希表中是否存在目标前缀和target，如果存在，则将其出现次数加到结果count中。
// 5. 将当前前缀和prefix_sum加入哈希表中，更新其出现次数。
class Solution
{
public:
    int subarraySum(vector<int> &nums, int k)
    {
        int count = 0;                   // 结果计数
        int pre = 0;                     // 当前前缀和
        unordered_map<int, int> pre_map; // 前缀和及其出现次数的哈希表   <前缀和, 出现次数>
        pre_map[0] = 1;                  // 初始化前缀和0的出现次数为1
        for (int i = 0; i < nums.size(); ++i)
        {
            pre += nums[i];             // 更新前缀和
            if (pre_map.count(pre - k)) // 检查目标前缀和是否存在
            {
                count += pre_map[pre - k]; // 更新结果计数
            }
            ++pre_map[pre - k]; // 更新当前前缀和的出现次数
        }
        return count; // 返回结果
    }
};
